
package main.old.new_2023.last.month_11;


/**
 * @Description: todo 2216. 美化数组的最少删除数
 * 给你一个下标从 0 开始的整数数组 nums ，如果满足下述条件，则认为数组 nums 是一个 美丽数组 ：
 * nums.length 为偶数
 * 对所有满足 i % 2 == 0 的下标 i ，nums[i] != nums[i + 1] 均成立
 * 注意，空数组同样认为是美丽数组。
 * 你可以从 nums 中删除任意数量的元素。当你删除一个元素时，被删除元素右侧的所有元素将会向左移动一个单位以填补空缺，而左侧的元素将会保持 不变 。
 * 返回使 nums 变为美丽数组所需删除的 最少 元素数目。
 *
 * todo 443. 压缩字符串
 * 给你一个字符数组 chars ，请使用下述算法压缩：
 * 从一个空字符串 s 开始。对于 chars 中的每组 连续重复字符 ：
 * 如果这一组长度为 1 ，则将字符追加到 s 中。
 * 否则，需要向 s 追加字符，后跟这一组的长度。
 * 压缩后得到的字符串 s 不应该直接返回 ，需要转储到字符数组 chars 中。需要注意的是，如果组长度为 10 或 10 以上，则在 chars 数组中会被拆分为多个字符。
 * 请在 修改完输入数组后 ，返回该数组的新长度。
 * 你必须设计并实现一个只使用常量额外空间的算法来解决此问题。
 *
 * @Author: Take-off
 * @Date: 1:00 PM 2023/6/
 * @Param:
 * @return:
 **/
public class Solution1121 {

    //压缩字符串
    public int compress(char[] cs) {
        int n = cs.length;
        int i = 0, j = 0;
        while (i < n) {
            int idx = i;
            while (idx < n && cs[idx] == cs[i]) idx++;
            int cnt = idx - i;
            cs[j++] = cs[i];
            if (cnt > 1) {
                int start = j, end = start;
                while (cnt != 0) {
                    cs[end++] = (char)((cnt % 10) + '0');
                    cnt /= 10;
                }
                reverse(cs, start, end - 1);
                j = end;
            }
            i = idx;
        }
        return j;

    }
    void reverse(char[] cs, int start, int end) {
        while (start < end) {
            char t = cs[start];
            cs[start] = cs[end];
            cs[end] = t;
            start++; end--;
        }
    }


    //美化数组的最少删除数
    public int minDeletion(int[] nums) {
        //使用 cnt 记录删除的元素 ，下标是 i-cnt
        int cnt = 0;
        int length = nums.length;
        for (int i = 0; i< length -1; i++){
            int num = nums[i];
            int target = i - cnt;
            if (target % 2 == 0 && nums[i] == nums[i + 1]){
                cnt += 1;
            }
        }
        if ((length - cnt) %2 == 1){
            cnt += 1;
        }
        return cnt;
    }

    public static void main(String[] args) {
        Solution1121 test = new Solution1121();
        char[] temp = {'a','b','b','b','b','b','b','b','b','b','b','b','b'};
        int i = test.compress(temp);
        System.out.println(i);
    }

}

